package org.lex.game.sudoku.model.builder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.lex.game.sudoku.model.DefaultSudokuModel;
import org.lex.game.sudoku.model.SudokuModel;
import org.lex.game.sudoku.model.SudokuModelListener.Cause;

import common.Sudokus;

public class ItEyeSudokuBuilder implements SudokuBuilder {
	public static void main(String[] args) {
		SudokuModel model = new DefaultSudokuModel();
		model.newGame(new ItEyeSudokuBuilder());
		System.out.print(model);
	}

	/** 生成随机数字的源数组，随机数字从该数组中产生 */
	private int[] num = null;

	public void build(SudokuModel model) {// 生成数字
		for (int row = 0, gridSize = model.getGridSize(); row < gridSize; row++) {
			// 尝试填充的数字次数
			int fillTimes = Sudokus.EMPTY_NUMBER;
			// 填充数字
			for (int col = 0; col < gridSize; col++) {
				// 产生数字
				model.set(Cause.SYSTEM, row, col, this.generateNum(fillTimes));
				// 如果返回值为0，则代表卡住，退回处理
				// 退回处理的原则是：如果不是第一列，则先倒退到前一列，否则倒退到前一行的最后一列
				if (Sudokus.EMPTY_NUMBER == model.get(row, col)) {
					if (col > 0) {
						// 不是第一列，则倒退一列
						col -= 2;
						continue;
					} else {
						// 是第一列，则倒退到上一行的最后一列
						row--;
						col = 8;
						continue;
					}
				}
				// 填充成功
				if (model.checkCell(row, col, false).isValid()) {
					// 初始化time，为下一次填充做准备
					fillTimes = 0;
				} else {
					// 继续填充, 次数增加1
					fillTimes++;
					// 继续填充当前格
					col--;
				}
			}
		}

		this.generateGame(model);
	}

	private void generateGame(SudokuModel model) {
		List<Integer> positions = new ArrayList<Integer>();
		for (int i = 0; i < 81; i++) {
			positions.add(i);
		}
		Collections.shuffle(positions);
		while (positions.size() > 0) {
			int position = positions.remove(0);
			int col = position % 9;
			int row = position / 9;
			int temp = model.get(row, col);
			model.set(Cause.SYSTEM, row, col, Sudokus.EMPTY_NUMBER);

			if (false == this.isValid(model, 0, new int[] { 0 })) {
				model.set(Cause.SYSTEM, row, col, temp);
			}
		}
	}

	private boolean isValid(SudokuModel model, int index, int[] numberOfSolutions) {
		if (index > 80)
			return ++numberOfSolutions[0] == 1;

		int col = index % 9;
		int row = index / 9;

		if (Sudokus.EMPTY_NUMBER == model.get(row, col)) {
			List<Integer> numbers = new ArrayList<Integer>();
			for (int i = 1; i <= 9; i++)
				numbers.add(i);

			while (numbers.size() > 0) {
				int number = getNextPossibleNumber(model, col, row, numbers);
				if (number == -1) {
					break;
				}
				model.set(Cause.SYSTEM, row, col, number);

				if (!isValid(model, index + 1, numberOfSolutions)) {
					model.set(Cause.SYSTEM, row, col, Sudokus.EMPTY_NUMBER);
					return false;
				}
				model.set(Cause.SYSTEM, row, col, Sudokus.EMPTY_NUMBER);
			}
		} else if (!isValid(model, index + 1, numberOfSolutions)) {
			return false;
		}
		return true;
	}

	private int getNextPossibleNumber(SudokuModel model, int col, int row, List<Integer> numbers) {
		while (numbers.size() > 0) {
			int number = numbers.remove(0);
			if (isPossibleX(model, row, number) && isPossibleY(model, col, number)
					&& isPossibleBlock(model, col, row, number))
				return number;
		}
		return -1;
	}

	private boolean isPossibleX(SudokuModel model, int row, int number) {
		for (int col = 0; col < 9; col++) {
			if (model.get(row, col) == number)
				return false;
		}
		return true;
	}

	/**
	 * Returns whether given number is candidate on y axis for given game.
	 * 
	 * @param game
	 *            Game to check.
	 * @param col
	 *            Position of y axis to check.
	 * @param number
	 *            Number to check.
	 * @return True if number is candidate on y axis, false otherwise.
	 */
	private boolean isPossibleY(SudokuModel model, int col, int number) {
		for (int row = 0; row < 9; row++) {
			if (model.get(row, col) == number)
				return false;
		}
		return true;
	}

	/**
	 * Returns whether given number is candidate in block for given game.
	 * 
	 * @param game
	 *            Game to check.
	 * @param col
	 *            Position of number on x axis in game to check.
	 * @param row
	 *            Position of number on y axis in game to check.
	 * @param number
	 *            Number to check.
	 * @return True if number is candidate in block, false otherwise.
	 */
	private boolean isPossibleBlock(SudokuModel model, int col, int row, int number) {
		int x1 = col < 3 ? 0 : col < 6 ? 3 : 6;
		int y1 = row < 3 ? 0 : row < 6 ? 3 : 6;
		for (int yy = y1; yy < y1 + 3; yy++) {
			for (int xx = x1; xx < x1 + 3; xx++) {
				if (model.get(yy, xx) == number)
					return false;
			}
		}
		return true;
	}

	/**
	 * 产生1-9之间的随机数字 规则：生成的随机数字放置在数组8-time下标的位置，随着time的增加，已经尝试过的数字将不会在取到
	 * 说明：即第一次次是从所有数字中随机，第二次时从前八个数字中随机，依次类推， 这样既保证随机，也不会再重复取已经不符合要求的数字，提高程序的效率
	 * 这个规则是本算法的核心
	 * 
	 * @param fillTimes
	 *            填充的次数，0代表第一次填充
	 * @return
	 */
	private int generateNum(int fillTimes) {
		// 第一次尝试时，初始化随机数字源数组
		if (fillTimes == 0) {
			this.num = new int[Sudokus.DEFAULT_GRID_SIZE];
			for (int i = 0; i < Sudokus.DEFAULT_GRID_SIZE; i++) {
				num[i] = i + 1;
			}
		}
		// 第10次填充，表明该位置已经卡住，则返回0，由主程序处理退回
		if (fillTimes == Sudokus.DEFAULT_GRID_SIZE) {
			return Sudokus.EMPTY_NUMBER;
		}
		// 不是第一次填充
		// 生成随机数字，该数字是数组的下标，取数组num中该下标对应的数字为随机数字
		int ranNum = (int) (Math.random() * (Sudokus.DEFAULT_GRID_SIZE - fillTimes));
		// 把数字放置在数组倒数第time个位置，
		int temp = num[Sudokus.DEFAULT_GRID_SIZE - 1 - fillTimes];
		num[Sudokus.DEFAULT_GRID_SIZE - 1 - fillTimes] = num[ranNum];
		num[ranNum] = temp;
		// 返回数字
		return num[Sudokus.DEFAULT_GRID_SIZE - 1 - fillTimes];
	}
}
